package com.xzz.sort;

import java.util.Arrays;

/**
 * @author: hhz
 * @create: 2021-12-31 09:31
 * 归并排序
 **/
public class MergeSort2 {
    // 用于辅助合并有序数组
    private static int[] temp;
    public static void main(String[] args) {
        int[] arr = new int[]{4, 6, 8, 5, 9, 2, 3, 7};
        temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void mergeSort(int[] arr, int left, int right) {

        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        // 先把 nums[lo..hi] 复制到辅助数组中
        // 以便合并后的结果能够直接存入 nums
        for (int i = left; i <= right; i++) {
            temp[i] = arr[i];
        }

        // 数组双指针技巧，合并两个有序数组
        int i = left, j = mid + 1;
        for (int p = left; p <= right; p++) {
            if (i == mid + 1) {
                // 左半边数组已全部被合并
                arr[p] = temp[j++];
            } else if (j == right + 1) {
                // 右半边数组已全部被合并
                arr[p] = temp[i++];
            } else if (temp[i] > temp[j]) {
                arr[p] = temp[j++];
            } else {
                arr[p] = temp[i++];
            }
        }
    }
}
